/************************************************************
 * DS_ALGORITHM.CPP                                14.09.2006
 *
 * .
 ************************************************************/
//#include <ap/settings/ds_settings.h>

#include "stdafx.h"
//#include "ap\ap_comm.h"
//#include "ap_prof.h"
//#include "ds_vector.h"
//#include "ds_string.h"
//#include "ds_algorithm.h"
//#include "m3d.h"

#ifdef _AP_XENON
#include <ppcintrinsics.h>
#endif

using namespace ds;

namespace {
const int PREPARE_PRIMES = 1000;
int maxPrime;

#ifdef _AP_XENON
__declspec (align(16)) BYTE reorder[64] = {
   1, 0,	3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14, 
   3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12,
   7, 6, 5, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8,
   15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 
};
#endif


/*************************************************************
 * sqr()
 * 
 *************************************************************/
inline int sqr(int val) { return val * val; }
}

/*************************************************************
* CheckPrime()
* 
*************************************************************/
bool ds::CheckPrime(int number)
{
   static osLOCK primeNumbersLock;
   static dsVECTOR<int> primeNumbers;

   // generate numbers up to PREPARE_PRIMES (allow to check numbers up to sqr(PREPARE_PRIMES))
   if (primeNumbers.IsEmpty()) {
      osLOCKER locker(primeNumbersLock);
      if (primeNumbers.IsEmpty()) {
         dsVECTOR<bool> v(PREPARE_PRIMES, false);

         for (int i = 2; i < PREPARE_PRIMES; ++i) {
            if (v[i]) {
               continue;
            }

            primeNumbers.PushBack(i);
            for (int k = i*2; k < PREPARE_PRIMES; k += i) {
               v[k] = true;
            }
         }

         // update max prime
         maxPrime = sqr(PREPARE_PRIMES);
         primeNumbers.Compact();
      }
   }

   // PREPARE_PRIMES^2 must be enough for our project
   // if this occurred - just change PREPARE_PRIMES
   STRONG_ASSERT(number <= maxPrime);

   // check if needed to generate more prime numbers
   if (number > maxPrime) {
      osLOCKER locker(primeNumbersLock);

      // mark this to disable recursion
      maxPrime = number;

      for (int i = primeNumbers[primeNumbers.Length()-1] + 1; sqr(i) < number; ++i) {
         if (CheckPrime(i)) {
            primeNumbers.PushBack(i);
         }
      }

      // update max prime
      maxPrime = number;
   }

   // check prime number
   for (int i=0; i < primeNumbers.Length() && sqr(primeNumbers[i]) <= number; ++i) {
      if (number % primeNumbers[i] == 0) {
         return false;
      }
   }

   return true;
}

/*************************************************************
 * ds::FindPrime()
 * 
 *************************************************************/
int ds::FindPrime(int minPrime)
{
   // check correct number
   if (minPrime < 0) {
      //ASSERT_ALOOF_CODE();
      minPrime = 1;
   }

   // generate prime numbers
   while (!CheckPrime(minPrime)) {
      ++minPrime;
   }
   return minPrime;
}

/*************************************************************
 * ds::MemHash()
 * 
 *************************************************************/
int ds::MemHash(const void * mem, int length)
{
   const BYTE * ptr = reinterpret_cast<const BYTE *> (mem);
   DWORD hash = 0;
   for (int i=0; i<length; ++i) {
      hash += (DWORD)ptr[i] << (i % 24);
   }

   return abs((int)hash);
}



/*************************************************************
* ds::ByteReorder()
* 
*************************************************************/
void ds::ByteReorder (BYTE *data, int size, int reorderGain)
{
   BYTE   tmp;
   int    i, j;

   if (reorderGain > 1) {
      ASSERT(size % reorderGain == 0);
#ifdef _AP_XENON
      if (!(size & 31) && !((DWORD)data & 15)) {
         __vector4* v1 = (__vector4*)data;
         __vector4 vt = {0};
         __vector4* v2 = (__vector4*)&reorder[(m3dLog2P2(reorderGain) - 1) * 16];
         for (int i = 0; i < size / 32; ++i) {
            *v1 = __vperm(*v1, vt, *v2);
            v1++;
            *v1 = __vperm(*v1, vt, *v2);
            v1++;
         }
         return;
      }
#endif      

      for (i = 0; i < size / reorderGain; i ++) {
         for (j = 0; j < reorderGain / 2; j ++) {
            tmp     = data[j];
            data[j] = data[reorderGain - j - 1];
            data[reorderGain - j - 1] = tmp;
         }
         data += reorderGain;
      }
   }
   return;
}

/**************************************************************************
* ds::ToString()                                                          *
*                                                                         *
**************************************************************************/
dsSTRING ds::ToString(const m3dV & val)
{
   return dsSPrintf("(%.2f, %.2f, %.2f)", val.x, val.y, val.z);
}

/******************************************************************************/
/* ds::ToString
/*
/******************************************************************************/
dsSTRING ds::ToString(const m4dV & val)
{
   return dsSPrintf("(%.2f, %.2f, %.2f, %.2f)", val.x, val.y, val.z, val.w);
}

/******************************************************************************/
/* ds::ToString
/*
/******************************************************************************/
dsSTRING ds::ToString(const m3dVTX & val)
{
   return dsSPrintf("(%.2f, %.2f)", val.s, val.t);
}

/**************************************************************************
* ds::ToString()                                                          *
*                                                                         *
**************************************************************************/
dsSTRING ds::ToString(int val)
{
   return dsSPrintf("%d", val);
}

/*************************************************************************/
/* ds::ToString 
/*
/*************************************************************************/
dsSTRING ds::ToString(long val)
{
   return dsSPrintf("%d", val);
}

/*************************************************************************/
/* ds::ToString 
/*
/*************************************************************************/
dsSTRING ds::ToString(unsigned long val)
{
   return dsSPrintf("%d", val);
}

/**************************************************************************
* ds::ToString()                                                          *
*                                                                         *
**************************************************************************/
dsSTRING ds::ToString(unsigned int val)
{
   return dsSPrintf("%u", val);
}

/**************************************************************************
* ds::ToString()                                                          *
*                                                                         *
**************************************************************************/
dsSTRING ds::ToString(float val)
{
   return dsSPrintf("%.3f", val);
}

/************************************
* ds::ToString
*
************************************/
dsSTRING ds::ToString(const m3dMATR& matr)
{
   return dsSPrintf("[0] = { %7.2f; %7.2f; %7.2f; %7.2f; }\n[1] = { %7.2f; %7.2f; %7.2f; %7.2f; }\n[2] = { %7.2f; %7.2f; %7.2f; %7.2f; }\n[3] = { %7.2f; %7.2f; %7.2f; %7.2f; }\n",
      matr._11, matr._12, matr._13, matr._14,
      matr._21, matr._22, matr._23, matr._24,
      matr._31, matr._32, matr._33, matr._34,
      matr._41, matr._42, matr._43, matr._44);
}


/************************************
* ds::ToString
*
************************************/
dsSTRING ds::ToString(const m3dBOX& box)
{
   return dsSPrintf("{ bll = %s, fur = %s }", ds::ToString(box.bll).CStr(), ds::ToString(box.fur).CStr());
}


/************************************
* ds::ToString
*
************************************/
dsSTRING ds::ToString(const m3dOBB& box)
{
   return dsSPrintf("org = %f; %f; %f;\nvx = %f; %f; %f;\nvy = %f; %f; %f;\nvz = %f; %f; %f;\nsize = %f; %f; %f;\n",
      box.GetOrg()->x, box.GetOrg()->y, box.GetOrg()->z,
      box.GetDirX()->x, box.GetDirX()->y, box.GetDirX()->z,
      box.GetDirY()->x, box.GetDirY()->y, box.GetDirY()->z,
      box.GetDirZ()->x, box.GetDirZ()->y, box.GetDirZ()->z,
      box.GetSizeX(), box.GetSizeY(), box.GetSizeZ());
}

/*************************************************************************/
/* ds::ToString 
/*
/*************************************************************************/
dsSTRING ds::ToString(const void * ptr)
{
   return dsSPrintf("0x%08d", ptr);
}

/**************************************************************************
* ds::CountFormatArguments()                                              *
*                                                                         *
**************************************************************************/
int ds::CountFormatArguments(const char * format, int type /*= -1*/)
{
   int count = 0;
   while (*format) {
      if (format[0] == '%') {
         if (format[1] == '%') {
            ++format;
         } else if (type == -1 || format[1] == type) {
            ++count;
         }
      }
      ++format;
   }

   return count;
}

#ifdef DS_DBG_CHECK_SHARED_PTR
dsVECTOR<DWORD*> dbgPtrList(AP_CL);
/**************************************************************************
* dsDBG_AddPtr()                                                          *
*                                                                         *
**************************************************************************/
void dsDBG_AddPtr (void* _ptr)
{
   DWORD* ptr = (DWORD*)_ptr;

   int idx = dbgPtrList.FindSorted(ptr);
   if (idx != -1) {
      *((int*)0) = 26;
   }
   STRONG_ASSERT(idx == -1);

   dbgPtrList.InsertSorted(ptr);
}

/**************************************************************************
* dsDBG_RemovePtr()                                                       *
*                                                                         *
**************************************************************************/
void dsDBG_RemovePtr (void* _ptr)
{
   DWORD* ptr = (DWORD*)_ptr;

   int idx = dbgPtrList.FindSorted(ptr);
   if (idx == -1) {
      *((int*)0) = 26;
   }
   STRONG_ASSERT(idx != -1);

   dbgPtrList.Erase(idx);
}

#endif

/******************************************************************************/
/* ds::SEARCH_PAIR::SEARCH_PAIR
/*
/******************************************************************************/
SEARCH_PAIR::SEARCH_PAIR(void)
   : lo(0), mid(0), hi(0)
{}

/******************************************************************************/
/* ds::SEARCH_PAIR::Init
/*
/******************************************************************************/
void SEARCH_PAIR::Init(int lo, int hi)
{
   this->lo = lo;
   this->hi = hi;
   mid = (hi + lo) / 2;
}

/******************************************************************************/
/* ds::SEARCH_PAIR::IsDone
/*
/******************************************************************************/
bool SEARCH_PAIR::IsDone(void) const
{
   return lo + 1 >= hi;
}

/******************************************************************************/
/* ds::SEARCH_PAIR::Step
/*
/******************************************************************************/
void SEARCH_PAIR::Step(bool result)
{
   if (IsDone()) {
      if (lo + 1 == hi) {
         if (result) {
            hi = mid = lo;
         } else {
            lo = mid = hi;
         }
      }

      return ;
   }

   if (result) {
      hi = mid;
   } else {
      lo = mid + 1;
   }

   mid = (lo + hi) / 2;
}

//
// End-of-file DS_ALGORITHM.CPP
//
